Computers utilize a wide variety of disks as storage media for user data. Disk technologies currently provide optical disks, magnetic disks, hard disks, floppy disks, and removable disks, and new disk technologies are being actively researched and developed. Indeed, some disks used by computers in the future may be cubical or some other shape rather than flat and circular. Investigation into "disks" in the form of non-volatile semiconductor storage devices such as flash memory is also ongoing.
FIG. 1 illustrates a disk 100 attached to a disk drive 102. The disk 100 illustrates physical characteristics of both floppies and hard disks; cubical disks or other disks may appear in different configurations than the one shown here. The disk 100 contains a number of concentric data cylinders such as the cylinder 104. The cylinder 104 contains several data sectors, including sectors 106 and 108. The sectors 106 and 108 are located on an upper side 110 of the disk 100; additional sectors may be located on a lower side 112 of the disk 100. The sides 110, 112 of the disk 100 define a platter 114. A hard disk may contain several platters. The upper side 110 of the disk 100 is accessed by a head 116 mounted on an arm 118 secured to the drive 102. Optical or cubical disks may be accessed by other means, such as photoemitters or photoreceptors.
A given sector on the disk 100 may be identified by specifying a head, a cylinder, and a sector within the cylinder. A triplet specifying the head number, cylinder number, and sector number in this manner is known as a "physical sector address." Alternatively, a given sector may be identified by a logical sector address, which is a single number rather than a triplet of numbers.
An operating system manages access, not only to the disk 100, but to other computer resources as well. Resources typically managed by the operating system include one or more disks and disk drives, memory (RAM and/or ROM), microprocessors, and I/O devices such as a keyboard, mouse, screen, printer, tape drive, modem, serial port, parallel port, or network port.
Many disks mold the available space into one or more partitions by using a partition table located on the disk. A wide variety of partitions are used, and more partition types will no doubt be defined over time. A partial list of current partitions and their associated file systems is given in U.S. Pat. No. 5,930,831 and incorporated here by reference. The list includes a variety of 12-bit, 16-bit, and 32-bit FAT file systems and numerous other file systems. Tools and techniques for manipulating FAT partitions and certain other partitions are described in U.S. Pat. Nos. 5,675,769, 5,706,472 and 5,930,831 assigned to PowerQuest Corporation, incorporated herein by this reference.
The NT File System ("NTFS") system provide useful features not available under many existing FAT file systems. Discussions of NTFS are provided in "Inside the Windows NT File System", by Helen Custer, ISBN 1-55615-660-X, and "Inside Windows NT" (Second Edition), by David A. Solomon, ISBN 1-57231-677-2, as well as in marketing and technical materials available in hard copy and on the Internet from Microsoft Corporation and other sources.
Some computer systems, such as many using NetWare FS or NTFS, mold disk storage into "segmented partitions" or "segmented volumes" with an approach somewhat different from that noted above. Segmented partitions are most often used in connection with file systems such as the Novell NetWare file system (NetWare is a mark of Novell), but may also be used with DOS (i.e., FAT) file systems and NTFS. The NetWare file system and related partition structures are discussed in U.S. Pat. No. 5,907,672; that discussion is incorporated herein. The NetWare file system is also discussed in marketing and technical materials available in hard copy and on the Internet from Novell and other sources.
On segmented systems, a "volume" is an instance of a file system. Hard drives may be divided into partitions, and volumes may be divided into "segments". A "segmented volume" is a volume which does or can contain segments, i.e., a segmentable volume. A "segmented partition" is a partition which does or can contain segments, i.e., a segmentable partition. For instance, a type 06 partition is not a segmented partition. A given partition may hold zero or more segments from zero or more volumes which are instances of one or more file systems; the cases of primary interest here are those in which one or more segments from one or more volumes are present.
The file system structures on disk do not necessarily reflect the presence of segments. Some NetWare FS structures can define the location and/or extent of segments, for example, but structures manipulated by NTFS routines do not ordinarily define segment extent or location. Segments may be created with conventional tools in order to improve response times or to provide fault tolerance. For example, in a Microsoft Windows NT environment, the Disk Administrator tool can be used to set up an NTFS volume that spans multiple disk drives. A NetWare partition is a section of a disk which is allocated to NetWare by a partition table. NetWare partitions may not span disks. Segmented partitions in other environments may be subject to the same or similar requirements. Although specific definitions of "disk" and "drive" are given herein, those of skill in the art will recognize that these terms are sometimes used interchangeably when the distinction between the media and the controller/drive mechanism is not important.
One partition table composition, denoted herein as the "IBM-compatible" partition table, which includes both the FAT file system and NTFS, is found on the disks used in many IBM.RTM. personal computers and IBM-compatible computers (IBM is a registered trademark of International Business Machines). Although IBM is not the only present source of personal computers, server computers, and computer operating systems and/or file system software, the term "IBM-compatible" is widely used in the industry to distinguish certain computer systems from other computer systems such as Macintosh computer systems produced by Apple (Macintosh is a mark of Apple Computer). IBM-compatible partition tables may be used on a wide variety of disks, with a variety of partition and file system types, in a variety of ways. They are generally used on 80.times.86 or Pentium-based architectures (Pentium is a mark of Intel), but may be used on computers with other CPU types.
As shown in FIG. 2, an IBM-compatible partition table 200 includes an Initial Program Loader ("IPL") identifier 202, four primary partition identifiers 204, and a boot identifier 206. As shown in FIG. 3, each partition identifier 204 includes a boot indicator 300 to indicate whether the partition in question is bootable. At most one of the partitions in the set of partitions defined by the partition table 200 is bootable at any given time. Some IBM-compatible computer systems allow "logical partitions" as well as primary partitions. All logical partitions are contained within one primary partition; a primary partition which contains logical partitions is known as an "extended partition."
Each partition identifier 204 also includes a starting address 302 which is the physical sector address of the first sector in the partition in question, and an ending address 304 which is the physical sector address of the last of the last sector in the partition. The start of a partition is sometimes referred to as the "left edge" or "beginning" and the end of the partition is sometimes referred to as the "right edge" or "ending" of the partition. A boot sector address 308 typically holds the logical sector address corresponding to the physical starting address 302.
Each partition identifier 204 also includes a system indicator 310. The system indicator 310 identifies the type of file system contained in the partition, which in turn defines the physical arrangement of user data and system data that is stored in the partition on the disk 100. Values not recognized by a particular operating system are treated as designating an unknown file system. The file system associated with a specific partition of the disk 100 determines the format in which data is stored in the partition, namely, the physical arrangement of user data and of file system structures in the portion of the disk 100 that is delimited by the starting address 302 and the ending address 304 of the partition in question. At any given time, each partition generally contains at most one type of file system, but a segmented partition may contain segments of different file systems.
It is sometimes desirable to combine two or more partitions on a computer disk by subsuming one or more partitions into another partition. The user data formerly found in the various partitions is now found in the resulting partition, and the subsumed partitions no longer exist (at least, they are not defined in the partition table 200 or in analogous volume definition tables in segmented partition systems).
A conventional approach to combining partitions begins by copying all necessary user and system data off the disk to a temporary storage location such as a tape or additional disk(s). The data copied includes without limitation the contents of files created by the user such as textual documents and spreadsheets (user data), the contents of files required to run applications such as word processors (more user data), and system data such as file system directory information, file allocation tables, and bad sector lists. Some internal file system data such as sector allocation maps may not need to be copied, but are often copied anyway. Familiar disk utilities such as FDISK, the install.nlm and nwconfig.nlm utilities in NetWare that manipulate partitions and volumes, and formatting utilities are then used to delete the partitions which are being subsumed and to increase the size of the result partition (thereby destroying some or all of the user data on the disk). Alternately, a tool such as the PowerQuest PartitionMagic or ServerMagic product can be used to resize the result partition once room is made available by removing the partitions which are being subsumed (PartitionMagic and ServerMagic are marks of PowerQuest). Finally, the data is copied back into the enlarged result partition. During the copying process the file system copy or restore utility creates appropriate new file system structures in the result reflecting the locations of copied data on the disk.
This approach to partition combination has several drawbacks. A temporary storage device with adequate storage capacity may not be readily available or affordable under the circumstances. Even if temporary storage is available, copying large amounts of data from the disk to temporary storage and then back again can take a substantial period of time. In addition, combining partitions in this manner is confusing and dangerous for many computer users. Users who are unfamiliar with the numerous technical details required as input to the conventional utilities may easily and inadvertently destroy data and/or make it necessary to further modify the disks with FDISK and/or other tools again, to reformat again, and to once again copy all the data from temporary storage into the reformatted partition. Even if everything works as desired the first time and FDISK is avoided in favor of a friendlier tool, combining partitions this way can be very time-consuming. With a typical disk holding several gigabytes of data the process may require several hours to complete successfully.
If the result partition has enough free space to accommodate the user data of the other partitions, or can be resized without removing all the other partitions, then some or all of the steps in resizing the result, backing up the user data, and restoring that user data into the result, can be skipped. But in many cases, the result will not have enough free space, with or without resizing. Moreover, copying user data from one partition to another can be time-consuming even if the data does not travel to and from tape during the copy.
Thus, it would be an advancement in the art to provide improved tools and techniques for combining partitions, including partitions that contain user data organized by FAT, NTFS, NetWare, or similar file systems.
Such improved tools and techniques are disclosed and claimed herein.